package com.clstu.tree;

/**
 * 演示顺序存储二叉树的使用  用数组模拟二叉树
 *  需要注意的是,完全二叉树才能这样存储!!!!!(因为根据自身下标计算子节点下标 和 父节点下标 的公式是针对完全二叉树的!!)
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        //测试
        int[] arr = {1,2,3,4,5,6,7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        System.out.println("前序遍历:");
        arrBinaryTree.preOrder(0);
        System.out.println("\n中序遍历:");
        arrBinaryTree.infixOrder(0);
        System.out.println("\n后续遍历:");
        arrBinaryTree.postOrder(0);
    }


}

/**
 * ArrBinaryTree,顺序存储二叉树类,
 * 维护的是一个数组,当做二叉树看待
 */
class ArrBinaryTree{
    private int[] arr;
    //构造器
    public ArrBinaryTree(int[] arr){
        this.arr = arr;
    }

    //需要注意的是,对完全二叉树才能使用顺序存储二叉树(下标公示就是针对完全二叉树的!!)
    //下标公式(注意:下标从0开始)
    // left = index*2+1
    // right = index*2+2
    // parent = (index-1)/2

    //编写方法实现顺序存储二叉树的前序遍历
    public void preOrder(int index){
        //思路分析:
        //前序遍历: 自己 ----> 左递归 ---> 右递归
        //需要注意的是,对完全二叉树才能使用顺序存储二叉树(下标公示就是针对完全二叉树的!!)
        //下标公式(注意:下标从0开始)
        // left = index*2+1
        // right = index*2+2
        // parent = (index-1)/2
        //自己
        System.out.print(arr[index]+"  ");
        //左递归
        if(index*2+1 < arr.length) {
            preOrder(index * 2 + 1);
        }
        //右递归
        if(index*2+2 < arr.length){
            preOrder(index*2+2);
        }
    }

    //编写方法实现顺序存储二叉树中序遍历
    public void infixOrder(int index){
        //中序遍历: 左递归 ---> 自己 ---> 右递归
        //左递归
        if(index*2+1< arr.length){
            infixOrder(index*2+1);
        }
        //自己
        System.out.print(arr[index]+"  ");
        //右递归
        if(index*2+2< arr.length){
            infixOrder(index*2+2);
        }
    }

    //编写方法实现顺序存储二叉树后序遍历
    public void postOrder(int index){
        //后序遍历:  左递归 ----> 右递归 ----> 自己
        //左递归
        if(index*2+1 < arr.length){
            postOrder(index*2+1);
        }
        //右递归
        if(index*2+2<arr.length){
            postOrder(index*2+2);
        }
        //自己
        System.out.print(arr[index]+"  ");
    }
}